package com.kk.datastructure.linkedlist.josepfu;

/**
 * title: 约瑟夫问题--单向环形链表
 * @author 阿K
 * 2020年11月28日 下午7:56:21 
 */
public class Josepfu {

	public static void main(String[] args) {
		// 测试一把构建环形链表，和遍历
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addKid(5);// 加入5个小鬼节点
		circleSingleLinkedList.showKid();

		// 测试一把小鬼出圈
		circleSingleLinkedList.countKid(1, 2, 5); // 2->4->1->5->3
	}
}

//创建一个环形的单向链表
class CircleSingleLinkedList {
	// 创建一个first节点,当前没有编号
	private Kid first = null;

	// 添加小鬼节点，构成一个环形链表(并非一个个添加，而是初始化个数)
	public void addKid(int nums) {
		if (nums < 1) {
			System.out.println("数量错误，无法构建环形");
			return;
		}
		// 辅助指针，帮助构建环形链表
		Kid curKid = null;

		// 使用for来创建我们的环形链表
		for (int i = 1; i <= nums; i++) {
			// 根据编号，创建小鬼节点
			Kid kid = new Kid(i);
			// 如果是第一个小鬼
			if (i == 1) {
				first = kid;
				first.setNext(first);// 构成环
				curKid = first; // 让curKid指向第一个小鬼
			} else {
				curKid.setNext(kid);// 此时的辅助是指向 first,它后面则指向 新节点(编号 2...)
				kid.setNext(first); // 构成环
				curKid = kid; // 此时curKid 指向第二个小鬼....
			}
		}
	}

	// 遍历当前环形链表
	public void showKid() {
		// 判空
		if (first == null) {
			System.out.println("没有任何小鬼~~");
			return;
		}

		// 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
		Kid curKid = first;
		while (true) {
			System.out.printf("小鬼的编号 %d \n", curKid.getNo());
			if (curKid.getNext() == first) {
				// 已经遍历结束
				break;
			}
			// 后移
			curKid = curKid.getNext();
		}
	}

	/**
	 * 开始抓鬼
	 * 
	 * @param startNo  表示从第几个小鬼开始数数
	 * @param countNum 表示每次数了几只小鬼(报数几)
	 * @param nums     表示最初圈内的总鬼数
	 */
	public void countKid(int startNo, int countNum, int nums) {
		// 数据校验
		if (first == null || startNo < 1 || startNo > nums) {
			System.out.println("参数输入有误， 请重新输入");
			return;
		}

		// 创建辅助指针，讨债鬼，作用催命
		Kid helper = first;// 初始化自己套自己，因为圈内目前就一个
		// 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
		while (true) {
			if (helper.getNext() == first) {
				// 已经到最后一个
				break;
			}
			// 后移
			helper = helper.getNext();
		}

		// 考虑到 可能不是 k=1的情况：
		// 小鬼报数前，先让 first 和 helper 移动 k - 1(startNo - 1)次
		for (int j = 0; j < startNo - 1; j++) {
			first = first.getNext();
			helper = helper.getNext();
		} 

		// 当小鬼报数时，让first 和 helper 指针同时 的移动 m - 1 次(countNum -1), 然后出圈
		// 这里是一个循环操作，直到圈中只有一个节点
		while (true) {
			if (helper == first) {
				// 说明圈中只有一个节点
				break;
			}
			// 让 first 和 helper 指针同时 的移动 countNum - 1
			for (int j = 0; j < countNum - 1; j++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			// 这时first指向的节点，就是要出圈的小鬼节点
			System.out.printf("小鬼%d出圈\n", first.getNo());
			// 这时将first指向的小鬼节点出圈
			first = first.getNext();
			helper.setNext(first); // 讨债鬼的绳索套在了新frist脖子上

		}
		System.out.printf("最后留在圈中的小鬼编号%d \n", first.getNo());
	}
}
//创建一个Kid类，表示一个节点
class Kid{
	private int no;// 编号
	private Kid next;// 指向下一个节点
	
	public Kid(int no) {
		this.no = no;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public Kid getNext() {
		return next;
	}
	public void setNext(Kid next) {
		this.next = next;
	}
}
